package cn.njutp.circle.DoubleQueue;
//双端队列
public class DeQueue<E> {

    E[] elements;

    private int front;

    private int size;

    public static final int DEFAULT_CAPACITY=10;

    public DeQueue(int capacity){
        capacity=capacity>DEFAULT_CAPACITY?capacity:DEFAULT_CAPACITY;
        this.elements=(E[])new Object[capacity];
    }

    public DeQueue(){
        this(DEFAULT_CAPACITY);
    }

    public void enQueueFromEnd(E element){
        ensureCapacity(size+1);
        elements[index(size)]=element;
        size++;
    }

    public void enQueueFromFront(E element){
        ensureCapacity(size+1);
        front=index(-1);
        elements[front]=element;
        size++;
    }

    /**
     * 扩容
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        if(capacity<elements.length)return;
        int newCapacity=this.elements.length<<1;
        E[] newElements=(E[])new Object[newCapacity];

        for (int i = 0; i < size; i++) {
            newElements[i]=elements[index(i)];
        }
        this.elements=newElements;
        front=0;
    }

    public E deQueueFromFront(){
        E ans=elements[front];
        elements[front]=null;
        front=index(1);
        size--;
        return ans;
    }

    public E deQueueFromEnd(){
        int index=index(size-1);
        E ans=elements[index];
        elements[index]=null;
        size--;
        return ans;
    }

    public void clear(){
        for (int i = 0; i < size; i++) {
            elements[index(i)]=null;
        }
        size=0;
        front=0;
    }

    public E peek(){
        return elements[front];
    }
    public boolean isEmpty(){
        return size==0;
    }

    public int size(){
        return size;
    }

    public int index(int index){
//        index可以是  size或者1
        index+=front;
        if(index<0){
            return index+ elements.length;
        }
        return index>= elements.length?index- elements.length:index;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("capcacity=").append(elements.length)
                .append(" size=").append(size)
                .append(" front=").append(front)
                .append(", [");
        for (int i = 0; i < elements.length; i++) {
            if (i != 0) {
                string.append(", ");
            }

            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
}
